package com.hr.leetcode.链表;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

/**
 * @author 周恒哲
 * @date 2020/05/04
 **/
public class _25_K个一组翻转链表 {
    //递归
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode first = head;
        int count = 0;
        while (first != null && count != k) {
            first = first.next;
            count++;
        }
        if (count == k) {
            first = reverseKGroup(first, k);
            while (count != 0) {
                count--;
                ListNode temp = head.next;
                head.next = first;
                first = head;
                head = temp;
            }
        }
        return head;
    }

    //迭代
    public ListNode reverseKGroup1(ListNode head, int k) {
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        pre.next = head;
        while (true) {
            int count = 0;
            ListNode temp = head;
            while (temp != null && count < k) {
                stack.add(temp);
                temp = temp.next;
                count++;
            }
            if (count != k) {
                pre.next = head;
                break;
            }
            while (!stack.isEmpty()){
                pre.next=stack.pollLast();
                pre=pre.next;
            }
            pre.next=temp;
            head=temp;
        }
        return dummy.next;
    }
}
